import java.util.Arrays;

/**
 * Created with IDEA
 * author:ju bai
 * Date:2021/1/30
 * Time:20:46
 **/
public class HeapDemo {
    public int[] elem;
    public int usedSize;
    public HeapDemo(){
        this.elem = new int[10];
    }

    /**
     * 为什么传 len
     * 每棵树的结束位置都是一样的
     * @param parent
     * @param len
     */
    public void adjustDown(int parent,int len){
        int child = 2*parent+1;
        while(child<len){//说明有左孩子
            if(child+1 < len && this.elem[child]<this.elem[child+1]){//child+1 < len:当前有右孩子
                child++;//child 下标一定是左右孩子的最大值
            }
            if(this.elem[child]>this.elem[parent]){
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else{
                break;//从最后一颗树开始向下调整
                //只要this.elem[child]<=this.elem[parent],就不需要循环了,后边已经是大堆了
            }
        }
    }
    public void createBigHeap(int[] array){
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
        //elem当中已经存放了元素
        for (int i = (this.usedSize-1-1)/2; i >=0 ; i--) {
            //eg:usedSize=10,下标从0开始,最后一个为9,为usedSize-1,孩子为n,父亲为(n-1)/2,为this.usedSize-1-1
            adjustDown(i,this.usedSize);
        }
    }
    public void show(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

    public boolean isFull(){
        return this.elem.length == this.usedSize;
    }

    /**
     * 放到数组的最后一个元素，然后向上调整
     * @param child
     */
    public void adjustUp(int child){
        int parent = (child-1)/2;
        while (child>0){
            if(this.elem[child]>this.elem[parent]){
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }
    public void push(int val){
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
        adjustUp(this.usedSize-1);
    }

    /**
     * 第一个和最后一个交换，向下调整0下标这棵树
     * @return
     */
    public int poll(){
        if(isEmpty()){
            throw new RuntimeException("队列为空！");
        }
        int ret = this.elem[0];
        int tmp = this.elem[0];
        this.elem[0] = this.elem[this.usedSize-1];
        this.elem[this.usedSize-1] = tmp;
        this.usedSize--;
        adjustDown(0,this.usedSize);
        return ret;
    }
    public boolean isEmpty(){
        return this.usedSize==0;
    }
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空！");
        }
        return this.elem[0];
    }

    public void heapSort() {
        int end = this.usedSize-1;
        while (end > 0) {
            int tmp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = tmp;
            adjustDown(0,end);
            end--;
          }
      }

}
